package LearnAlgorithm.f_字符串;

import java.util.Arrays;


public class n字符串匹配SuffixArrayNotStatic {
    public static void main(String[] args) {
        String mother = "ABABABABB";
        String child = "BABB";
        new n字符串匹配SuffixArrayNotStatic().suffixArrayMatch(mother, child);
    }

    /**
     * O(N*N*logN + N*logM)
     * @param mother
     * @param child
     */
    public void suffixArrayMatch(String mother, String child) {
        Suff[] suffixArray = makeSuffixArray(mother);//O(N*N*logN)
        int l = 0;
        int r = mother.length() - 1;
        //O(NlogM)
        while (r >= l) {//开始二分查找；必须>=，是为了保证索引1和最后的索引，这两个元素也能参与比较
            int mid = l + ((r - l) >>> 1);
            int compareResult;
            String suffMid = suffixArray[mid].getString();
            if (suffMid.length() >= child.length()) {
                compareResult = suffMid.substring(0, child.length()).compareTo(child);
            } else {
            	//为什么suffMid比child长度小还要比呢？它俩肯定是不相同的啊。
            	//是因为二分查找；注意这是在查找过程中；我们知道肯定不相同，我们的目的是利用二分查找特性进行下一次查找。
                compareResult = suffMid.compareTo(child);
            }
            if (compareResult == 0) {
                System.out.println(suffixArray[mid].getIndex());//找到了
                return;
            } else if (compareResult < 0) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        System.out.println("没找到,输出所有的后缀数组：");
        printSuffixArray(suffixArray);
    }

    /**
     * O(N^2*logN)
     * suffixArray[i].getIndex = k
           * 表示在后缀数组suffixArray中，排名是i(索引)的“后缀”，是从原串的第k索引开始的
     * @param string
     * @return
     */
    public Suff[] makeSuffixArray(String string) {
        int length = string.length();
        Suff[] suffixArray =  new Suff[length];
        for (int i = 0; i < length; i++) {//填入内容
            String substring = string.substring(i);
            suffixArray[i] = new Suff(substring, i);//substring(i);去掉前i个字符，剩下的作为新的字符串
        }
        Arrays.sort(suffixArray);//O(NlogN)；排序
        return suffixArray;
    }

    /**
	 * 打印Suff[]
	 * @param arr
	 */
	public void printSuffixArray(Suff[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
    
    /**
	     * 自定义包含string,index的对象
	     * 并且实现比较方法
     * @author wuqiu
     */
    public class Suff implements Comparable<Suff> {
        private String string = null;//后缀内容
        private int index = 0;//后缀起始下标
        public Suff() {};
        public Suff(String string, int index) {
            this.string = string;
            this.index = index;
        }
        public void setString(String string) {
            this.string = string;
        }
        public String getString() {
            return this.string;
        }
        public void setIndex(int index) {
            this.index = index;
        }
        public int getIndex() {
            return this.index;
        }
        @Override
        public int compareTo(Suff other) {//O(N)
			/*
			this是新元素，other是老元素
			this.string.compareTo(other.string)会返回一个int A
			Suff类的compareTo会返回一个int,实际上就是把A返回
			在使用了自然排序的集合中添加Suff类对象
			这些对象的顺序是根据A决定的
			A = 0，在有些集合中，新元素(this)就不会加入
			A > 0，this在other后面加入
			A < 0，this在other前面加入
			 */
            return this.string.compareTo(other.string);
        }
        @Override
        public String toString() {
            return "Suff {" +
                    "string='" + string + '\'' +
                    ", index=" + index +
                    '}';
        }
    }
}
